Solid modelling underlies many aspects of computer-aided design and analysis, physical process simulation, robotics, computer vision and other computer-related tasks. Computational experiments using analogs of real processes, as applied to computer representations of physical objects, reduce the need for costly experimentation and prototyping of preliminary designs. Such experiments often require substantial amounts of computer time. Reduction of the processing time for such experiments allows more design alternatives to be examined in greater detail.
Three-dimensional objects or solids are most often represented using three fundamentally different schemes: Constructive Solid Geometry which describes a solid as an algebraic combination of primitive solids using set operations; Volumetric Decomposition which describes a solid as a disjoint union of simple solids; and Boundary Representation which describes a solid by enumerating zero, one, and two-dimensional portions of its boundary.
Set operations are of fundamental importance for all three kinds of representations. Independent of the basic representation of an object, all known set-operation algorithms require boundary representations or equivalent computations. Those set-operation algorithms require large amounts of computation time for several reasons. The algorithms are inherently intricate and this alone leads to long computation times. Moreover, interesting models tend to be large, and the computation times are a function of the size of the model.
Parallel computation using highly parallel processors has been suggested as a panacea for time-consuming computations,since it offers a way to increase the amount of computation power available as problem size increases. Special-purpose parallel computers have been built for modelling applications in computer graphics, but have not been shown to be useful for solid modelling applications. Such computers have been designed primarily to assist in the rendering of computer graphics images and not for the manipulation of the underlying representation of the geometric objects. Recently, a parallel architecture and related algorithms for solid modelling have been proposed which use load-balancing to distribute the work over a small number of very powerful processors. Such a solution does not appear to be scalable with problem size due to the cost involved in replicating such powerful processors.
Today, massively parallel processing systems have become available in the marketplace. For instance, the "Connection Machine" marketed by Thinking Machines, Inc., Cambridge, Mass. employs 65,536 processors, each processor being of limited capability and memory size. The processors are treated as an array by a front-end computer where a program is resident that controls the processors to carry out a highly parallel algorithm. It is important in such massively parallel systems, during the execution of a program, to avoid intercommunication between processors in the array. Such communications significantly slow the overall execution of an algorithm and, in some instances, render questionable the value of the massively parallel system (as compared to a serial system).
Solid or three-dimensional modelling algorithms employ a number of known data representations. A "solid" is a physical object whose boundary consists of planar pieces. Objects whose boundaries have curved surfaces are generally approximated using planar facets. Thus, a solid is described by planar pieces called faces; the line segments where faces meet are called edges; and the points where edges meet are termed vertices.
Complicated solids are formed by combining simpler solids, using operations such as union, intersection and difference. Practical computations on solids operate on the boundary representations of solids. Such calculations require relationships to be defined among the vertices, edges and faces. Such relationships are called "adjacencies".
Referring to FIG. 1, a cube is shown having six faces (A-F), 12 edges and 8 vertices. To accomplish the modelling and manipulation of the cube, a set of interrelated data structures has been suggested in the prior art (see Karasick, "On The Representation and Manipulation of Rigid Solids", PhD Thesis, McGill University, Montreal, Quebec, 1988; available as Cornell University Department of Computer Science Report 89-976, Ithaca, N.Y.). In that thesis, a Star-edge data structure is described for boundary representations of a solid, that is particularly useful in a serial computing environment. Karasick suggests that an additional artifact be added to the model to better enable the description of the solid. That added artifact is termed a directed edge (or d-edge). D-edges are shown in FIG. 1 in each of faces A-F. For instance, face A has d-edges 0-3; face B has d-edges 4-7, etc. It is to be noted in FIG. 1, that each edge of the cube (e.g., edge e between vertices u, v) has two associated d-edges, (i.e., 2 and 4) and each such d-edge respectively resides in a plane that contains edge e.
An edge e with Initial vertex u and Terminal vertex v can bound many faces. For each adjacent face f, it is necessary to describe whether the interior of face f is to the left or right of edge e. This is implemented using d-edges e.sub.f (+) and e.sub.f (-). D-edge e.sub.f (+) exists if the interior of face f is to the right of e. The left and right directions from edge e are determinable by standing at the Initial Vertex u of edge e and looking to its Terminal Vertex v. D-edge e.sub.f (-) exists if face f is to the left. More precisely, if N is an outward normal of face f, then e.sub.f (+) exists if (v-u).times.N points from the interior of e into the interior of f. Similarly, e.sub.f (-) exists if (u-v).times.N points from the interior of e into the interior of face f. D-edge e.sub.f (+) has Initial Vertex u and Terminal Vertex v. D-edge e.sub.f (-) has Initial Vertex v and Terminal Vertex u. In FIG. 1 (and FIG. 4) d-edges are represented as direction vectors.
D-edges incident to a vertex v and contained in a face f, are ordered by radially sorting their direction vectors in the plane of face f. Likewise, the d-edges associated with an edge e are ordered by radially sorting, about edge e, the faces in which they respectively reside.
The key adjacency relationships of the Star-edge representation are shown in FIG. 2. The Star-edge representation is conceptually straightforward, yet its realization as a data structure is complicated and difficult to implement efficiently.
It can be seen from FIG. 2 that each of three independent data sets, i.e., edges, faces, and vertices, has pointers both to d-edges associated with each face and, in two instances, pointers to each other. Such a data representation requires a large number of memory references each time a modeling algorithm is formed. Such a representations does not lend itself to highly parallel processing.
Accordingly, it is an object of this invention to provide an improved data structure for representing three-dimensional objects on parallel computing systems.
It is another object of this invention to provide a massively parallel architecture computing system with a data structure that enables highly parallel, processor-independent, modelling operations.
It is still another object of this invention to provide an improved method for assigning labels to a data representational structure of a model that enables a highly parallel architecture to operate with minimal inter-processor communications.